'''给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
'''
# 定义节点
class Node:
    def __init__(self, item=0,next=None):
        self.elem = item   # elem是节点的元素域 , item是保存在元素域里的元素
        self.next = next   # next是节点的链接域
class LinkedList:
     # 初始化这个类对象，要表示是一个空链
    def __init__(self,node:Node):
        if Node==None:
            self.head=None
        else:
            self.head=node
    # 在链表头部添加元素(头插法)
    def add(self, item):
        # 创建一个保存item值的节点（新节点）
        node = Node(item)

        # 将新节点的链接域next指向到头节点，即head指向的位置
        node.next = self.head

        # 将链表的头结点self.head指向新节点node
        self.head = node
    def is_empty(self):
        return self.head==None
   
# 在链表尾部添加元素(尾插法)
    def append(self, item):
        # 创建一个保存item值的节点（新节点）
        node = Node(item)

        # 判断链表是否为空
        '''
        若是空链表,则将head指向新节点;
        若不是空链表,则找到尾部,将尾节点的next指向新节点
        '''
        if self.is_empty():
            self.head = node
        else:
            # 创建一个游标(指针cur),指向头结点
            cur = self.head
            # 移动指针，直到找到尾节点
            while cur.next != None:
                # 指针向后移动
                cur = cur.next

            # 跳出循环，此时cur所在的位置就是链表的最后一个节点
            # 那就把 cur 的next指向到 新节点
            cur.next = node
# 通过列表创建链表
    def createLinkedList(self,l:list): 
        for i in l:
            self.append(i)
     #逆序链表   
    def reverseOrder(self):
        t= LinkedList(None)
        cur=self.head
        while cur != None:
            t.add(cur.elem)
            cur=cur.next
        return t
    # 遍历整个链表
    def travel(self):
        # 判断链表是否为空
        if self.is_empty():
            print('空链表!!!')
        else:
            # 创建一个游标(指针cur),指向头结点
            cur = self.head

            # 移动指针，打印每一个节点的元素
            while cur != None:
                print(cur.elem, end=' ')
                cur = cur.next
'''
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
'''
class Solution:
    #初始化
    def __init__(self,node:Node):
        if Node==None:
            self.head=None
        else:
            self.head=node
    def addTwoNumbers(self,l1:Node,l2:Node) ->Node:
        #判断如果出现空值的情况
        if l1==None:
            return l2
        if l2==None:
            return l1
        #变量定义 
        #result：结果指针 carry:进位 p：游标指针
        result=Node()
        p=result
        carry =0
        #当位数相同的时候
        while l1 and l2 :
            #l1.elem 与l2.elem是指当前位的数值
            #第一次进入循环时，l1与l2都是个数
            #生成新的结点，让p.next指向它。
            p.next=Node((l1.elem+l2.elem+carry)%10)
            carry=(l1.elem+l2.elem+carry)//10
            #l1,l2进入到下一轮
            l1=l1.next
            l2=l2.next
            #p向前进,下面这句特别重要。结果存在result.next,而不是result
            p=p.next
        #如果l2比l1长
        if l2:
            while l2:
                p.next=Node((l2.elem+carry)%10)
                carry=(l2.elem+carry)//10
                l2=l2.next
                p=p.next
        #如果l1比l2长
        if l1:
            while l1:
                p.next=Node((l1.elem+carry)%10)
                carry=(l1.elem+carry)//10
                l1=l1.next
                p=p.next
        #如果最后还有进位
        if carry==1:
            p.next=Node(1)
        #返回
        return result.next
    def is_empty():
        return self.head==None
        # 遍历整个链表
    def travel(self):
        # 判断链表是否为空
        if self.is_empty():
            print('空链表')
        else:
            # 创建一个游标(指针cur),指向头结点
            cur = self.next

            # 移动指针，打印每一个节点的元素
            while cur != None:
                print(cur.elem, end=' ')
                cur = cur.next


if __name__ == '__main__':

   
    l1=input("输入长整数1的值：").split(" ")
    l1=[int(l1[i]) for i in range(len(l1))]
    l2=input("输入长整数2的值：").split(" ")
    l2=[int(l2[i]) for i in range(len(l2))]
    t1=LinkedList(None)
    t1.createLinkedList(l1)
    t2=LinkedList(None)
    t2.createLinkedList(l2)
    print("\n长整数1:\n")
    t3=t1.reverseOrder()
    t1.travel()
    print("\n长整数2:\n")
    t4=t2.reverseOrder()
    t2.travel()
    s=Solution(None)
    p=s.addTwoNumbers(t3.head,t4.head)
    pp=LinkedList(p)
    print("\n输出相加的结果：\n")
    pp=pp.reverseOrder()
    pp.travel()
    print("\n\n\n")
    t1.travel()
    print("+")
    t2.travel()
    print("=")
    pp.travel()
    
  